#define DEBUG
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=80000, maxk=17;

bool cmp(int *a, int *b) {
	return *a<*b;
}

void remap(int n, int a[], int map[]) {
	static int *p[maxn+1];
	for (int i=1; i<=n; i++) p[i] = a+i;
	sort(p+1, p+n+1, cmp);
	int now=1, t=*p[1];
	for (int i=1; i<=n; i++) {
		int temp=*p[i];
		now += temp!=t;
		*p[i] = now;
		t = map[now] = temp;
	}
}

class CT {
	public:
		CT *left, *right;
		int v;

		CT() {
			v=0, left = right = 0;
		}

		int getV() {
			return this ? v : 0;
		}

		CT* getLeft() {
			return this ? left : 0;
		}

		CT* getRight() {
			return this ? right : 0;
		}

		void merge() {
			v = left->getV()+right->getV();
		}

		CT* add(int t, int tv, int l, int r) {
			CT *ret = new CT();
			if (l==r) {
				ret->v = tv+getV();
			} else {
				int mid=(l+r)/2;
				if (t<=mid) {
					ret->left = getLeft()->add(t, tv, l, mid);
					ret->right = getRight();
				} else {
					ret->right = getRight()->add(t, tv, mid+1, r);
					ret->left = getLeft();
				}
				ret->merge();
			}
			return ret;
		}

		static int getKth(CT *a, CT *b, CT *x, CT *y, int k, int l, int r) {
			if (l==r) return l;
			else {
				int size=a->getLeft()->getV()+b->getLeft()->getV()-x->getLeft()->getV()-y->getLeft()->getV();
				int mid=(l+r)/2;
				if (size>=k) {
					return getKth(a->getLeft(), b->getLeft(), x->getLeft(), y->getLeft(), k, l, mid);
				} else {
					return getKth(a->getRight(), b->getRight(), x->getRight(), y->getRight(), k-size, mid+1, r);
				}
			}
		}
};

class Tree {
	public:
		int n, m, ind[maxn+1], to[2*maxn-1], link[2*maxn-1], f[maxn+1][maxk+1], v[maxn+1], dep[maxn+1];
		CT *rank[maxn+1];

		void addSide(int u, int v) {
			m++;
			to[m] = v;
			link[m] = ind[u];
			ind[u] = m;
		}

		void build(int o, int fa) {
			rank[o] = rank[fa]->add(v[o], 1, 1, n);
			dep[o] = dep[fa]+1;
			f[o][0] = fa;
			for (int i=1; i<=maxk; i++) {
				f[o][i] = f[f[o][i-1]][i-1];
			}

			for (int i=ind[o]; i; i=link[i]) {
				if (to[i]!=fa) {
					build(to[i], o);
				}
			}
		}

		int lca(int u, int v) {
			if (dep[u]<dep[v]) swap(u, v);
			for (int i=maxk; i>=0; i--) {
				if (dep[f[u][i]]>=dep[v]) u=f[u][i];
			}
			if (u==v) return u;
			for (int i=maxk; i>=0; i--) {
				if (f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i];
			}
			return f[u][0];
		}
};

int main() {
#ifdef DEBUG
	freopen("src.in", "r", stdin);
	freopen("src.out", "w", stdout);
#endif

	static Tree tree;
	static int map[maxn+1];
	int testcase, n, m, t;
	scanf("%d %d %d %d", &testcase, &n, &m, &t);
	tree.n = n;
	for (int i=1; i<=n; i++) scanf("%d", tree.v+i);
	remap(n, tree.v, map);

	for (int i=1; i<=m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		tree.addSide(x, y);
		tree.addSide(y, x);
	}
	for (int i=1; i<=n; i++) {
		if (!tree.dep[i]) tree.build(i, 0);
	}

	for (int i=1, lastans=0; i<=t; i++) {
		int x, y, k;
		char opt;
		scanf(" %c %d %d", &opt, &x, &y);
		x^=lastans, y^=lastans;
		if (opt=='Q') {
			scanf("%d", &k);
			k^=lastans;
			int t=tree.lca(x, y);
			printf("%d\n", lastans=map[CT::getKth(tree.rank[x], tree.rank[y], tree.rank[t], tree.rank[tree.f[t][0]], k, 1, n)]);
		} else {
			tree.addSide(x, y);
			tree.addSide(y, x);
			if (tree.rank[x]->getV()>tree.rank[y]->getV()) tree.build(y, x);
			else tree.build(x, y);
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}
